# encoding:utf-8

import picross_functions as pfun
import numpy
import sys
import datetime as dt
import copy

start_time = dt.datetime.now()

# s_in_size : 行数 x 列数
# s_in_row ： 每行的绘图值
# s_in_column : 每列的绘图值
# 读取上述输入参数
map_file = open('map.txt', mode='r', encoding='utf-8')
a = map_file.readline()
while a and a != 'r\n':
    a = map_file.readline()

a = map_file.readline()
s_in_row = []
while a and a != 'c\n':
    if a == '\n':
        s_in_row.append([])
        a = map_file.readline()
        continue
    t = eval(a)
    if type(t) == int:
        s_in_row.append([t])
    else:
        s_in_row.append(list(t))
    a = map_file.readline()

a = map_file.readline()
s_in_column = []
while a:
    if a == '\n':
        s_in_column.append([])
        a = map_file.readline()
        continue
    t = eval(a)
    if type(t) == int:
        s_in_column.append([t])
    else:
        s_in_column.append(list(t))
    a = map_file.readline()

map_file.close()

s_in_size = [len(s_in_row), len(s_in_column)]

# 初始化结果图
temp_map = [-1 for i in range(s_in_size[1])]
resu_map = [temp_map.copy() for i in range(s_in_size[0])]

# todo : 容错
# 检查行列数是否有问题，检查输入参数是否小于等于行列数

# 求解 - 递归
# 计算所有行列的可能性，对可能性数量进行排序
# 如果存在可能性为0的行，退出本次递归
# 如果所有行列都已经剔除，则为找到解
# 选择可能性最少的行或列，遍历尝试改变，并进入下一层递归
# 改变过程
#   记录下结果，并剔除该行或列
#   如果所有的解有共同的结果，也记录下结果。
# 避免死循环：经过一轮循环之后，没有剔除任何行列

# 待解的行与列
row_loop = [i for i in range(s_in_size[0])]
column_loop = [i for i in range(s_in_size[1])]

# 最终是否找到解
have_solutions = False
resu_map_solution = []


def find_next(rl, cl, map_now):
    # 声明全局变量
    global resu_map_solution

    # # 校验节点
    # print("\nmap_now")
    # for i in map_now:
    #     print(i)
    # print('rl,',rl)
    # print('cl,',cl)

    # 复制当前参数，避免在原处修改造成影响
    new_map = copy.deepcopy(map_now)

    p_find = False  # 是否找到有唯一解的行或列
    p_find_position = []  # 解在哪一行或列
    p_find_min = 99  # 过程量：最小可能性
    p_find_solutions = []  # 解所在行或列的所有可能性

    for i in rl:
        # 遍历所有行
        p_solutions = pfun.line_solutions(s_in_size[0], new_map[i], s_in_row[i])
        p_solutions_len = len(p_solutions)
        if p_solutions_len == 0:
            return False
        if p_solutions_len == 1:
            # 有唯一解进行记录，并跳出循环
            p_find = True
            p_find_min = 1
            p_find_position = ['r', i]
            p_find_solutions = p_solutions
            break
        elif p_solutions_len < p_find_min:
            # 记录最少可能性
            p_find_min = p_solutions_len
            p_find_solutions = p_solutions
            p_find_position = ['r', i]
    if not p_find:
        # 没找到唯一解的情况下，遍历所有列
        for i in cl:
            p_line = list(numpy.array(new_map)[:, i])
            p_solutions = pfun.line_solutions(s_in_size[1], p_line, s_in_column[i])
            p_solutions_len = len(p_solutions)
            if p_solutions_len == 0:
                return False
            if p_solutions_len == 1:
                # 记录唯一解，并跳出循环
                p_find_min = 1
                p_find_position = ['c', i]
                p_find_solutions = p_solutions
                break
            elif p_solutions_len < p_find_min:
                # 记录最少可能性
                p_find_min = p_solutions_len
                p_find_solutions = p_solutions
                p_find_position = ['c', i]

    # # 校验
    # print('min:',p_find_min)
    # print('position:',p_find_position)
    # print('solution:',p_find_solutions)

    if p_find_position[0] == 'r':
        # 如果找到的最少解是行
        # 把所有可能性中的固定项记录下来
        for j in range(s_in_size[1]):
            value_j = p_find_solutions[0][j]
            p_same = True
            for k in p_find_solutions[1:]:
                if k[j] != value_j:
                    p_same = False
                    break
            if p_same:
                new_map[p_find_position[1]][j] = value_j
        # 循环尝试所有的解
        for k in p_find_solutions:
            for j in range(s_in_size[1]):
                new_map[p_find_position[1]][j] = k[j]
            new_rl = copy.deepcopy(rl)
            new_rl.remove(p_find_position[1])
            if len(new_rl) + len(cl) == 0:
                resu_map_solution = new_map
                return True
            if find_next(new_rl, cl, new_map):
                return True
    else:
        # 如果找到的是列
        # 把所有可能性中的固定项记录下来
        for j in range(s_in_size[0]):
            value_j = p_find_solutions[0][j]
            p_same = True
            for k in p_find_solutions[1:]:
                if k[j] != value_j:
                    p_same = False
                    break
            if p_same:
                new_map[j][p_find_position[1]] = value_j
        # 循环尝试所有的解
        for k in p_find_solutions:
            for j in range(s_in_size[0]):
                new_map[j][p_find_position[1]] = k[j]
            new_cl = copy.deepcopy(cl)
            new_cl.remove(p_find_position[1])
            if len(rl) + len(new_cl) == 0:
                resu_map_solution = new_map
                return True
            if find_next(rl, new_cl, new_map):
                return True

    return False


p_resu = find_next(row_loop, column_loop, resu_map)

# 打印结果
if p_resu:
    print('图形如下：')
    for i in resu_map_solution:
        print(i)
else:
    print('无解')

end_time = dt.datetime.now()

print('耗时：', end_time - start_time)
